/*
给定一个二叉搜索树和一个目标结果，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true


输入: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 9
输出: True


输入: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 28
输出: False


二叉搜索树是一个有序结构，很容易联想到有序数组的两数之和，有序数组的两数之和的经典解法是双指针，这道题也可以用相同思路解决。
要使用双指针，需要用两个指针分别从小到大、从大到小遍历，在二叉搜索树中分别对应中序遍历和反中序遍历（把中序遍历中的left和right互换），这里用 C++ 的成员指针写了个统一算法解决


*/

//
template <TreeNode *TreeNode::*ls = &TreeNode::left, TreeNode *TreeNode::*rs = &TreeNode::right>
void tree_iterator_init(TreeNode *&it, stack<TreeNode *> &st)
{
    while (it->*ls)
    {
        st.push(it);
        it = it->*ls;
    }
}

template <TreeNode *TreeNode::*ls = &TreeNode::left, TreeNode *TreeNode::*rs = &TreeNode::right>
void tree_iterator_next(TreeNode *&it, stack<TreeNode *> &st)
{
    if (it->*rs)
    {
        it = it->*rs;
        tree_iterator_init<ls, rs>(it, st);
    }
    else if (!st.empty())
    {
        it = st.top();
        st.pop();
    }
    else
        it = nullptr;
}

class Solution
{
public:
    bool findTarget(TreeNode *root, int k)
    {
        if (!root)
            return false;
        auto it1 = root;
        auto it2 = root;
        stack<TreeNode *> st1;
        stack<TreeNode *> st2;
        tree_iterator_init<&TreeNode::left, &TreeNode::right>(it1, st1);
        tree_iterator_init<&TreeNode::right, &TreeNode::left>(it2, st2);
        while (it1 != it2)
        {
            const int sum = it1->val + it2->val;
            if (sum == k)
                return true;
            if (sum < k)
                tree_iterator_next<&TreeNode::left, &TreeNode::right>(it1, st1);
            else
                tree_iterator_next<&TreeNode::right, &TreeNode::left>(it2, st2);
        }
        return false;
    }
};
